package sword.chapter8Tree;

import java.util.Stack;

/**
 * 展平二叉搜索树
 * <p>
 * 要点
 * 中序遍历符合二叉搜索树的排序顺序
 * 1. 遍历每一个节点时，需要将上一个节点的右节点指向当前节点，左节点设置为null
 * 2. first记录第一个节点并作为最后返回结果
 *
 * @author K
 * @date 2021-12-12 17:07
 */
public class S52IncreasingBST {
    public static TreeNode s52(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        TreeNode first = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();

            if (prev != null) {
                prev.right = cur;
            } else {
                first = cur;
            }
            prev = cur;
            cur.left = null;
            cur = cur.right;
        }

        return first;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        TreeNode node6 = new TreeNode(6);
        root.left = node2;
        root.right = node5;
        node2.left = node1;
        node2.right = node3;
        node5.right = node6;

        TreeNode result = s52(root);
        System.out.println();
    }
}
